Wrocławskie ZOO
Limit pamięci: 32 MB
We wrocławskim ZOO jest bram wejściowych oznaczonych numerami , wybiegów dla zwierząt oznaczonych numerami oraz bram wyjściowych oznaczonych numerami .
W ZOO są ścieżki prowadzące od bram wejściowych do wybiegów, pomiędzy wybiegami i od wybiegów do bram wyjściowych.
Ścieżki w ZOO nie przecinają sie ze sobą (jest to możliwe, gdyż niektóre ścieżki biegną tunelami lub wiszącymi mostami) i są dwukierunkowe.
Dzieci ze szkoły w Ziębicach wybierają się na lekcję przyrody do ZOO.
Pani nauczycielka wyznaczyła kilku (dokładnie ) uczniów i zleciła im przygotowanie w domu referatów dotyczących wybranych zwierząt.
Pani zaplanowała wycieczkę po ZOO tak, by odwiedzić wybiegi wszystkich
opisywanych przez nauczycielkę zwierząt, kierując się
następującymi kryteriami.
Trasa:
- może rozpoczynać się od dowolnej bramy wejściowej,
- musi odwiedzać wybiegi wszystkich wskazanych zwierząt,
- może kończyć się przy dowolnej bramie wyjściowej,
- nie może w trakcie (oprócz początku i końca) przebiegać przez żadną bramę,
- ma być jak najkrótsza, tzn.
przebiegać przez jak najmniejszą liczbę wybiegów.
Niestety w ostatniej chwili pojawił się dodatkowy problem.
Okazało się, że dzieci ułożyły swoje referaty w jedną długą opowieść o wybranych zwierzętach i teraz trzeba odwiedzić wybiegi w kolejności wyznaczonej przez tę opowieść i na dodatek, by nie psuć efektu, nie można odwiedzić żadnego ze zwierząt, zanim nie nadejdzie jego pora w opowieści.
Tak więc doszedł dodatkowy warunek:
- trasa nie może dotrzeć do wybiegu -tego z wybranych zwierząt, zanim nie odwiedzi wybiegu zwierzęcia .
Zadanie
Napisz program który:
- wczytuje liczby: bram wejściowych, wybiegów, bram wyjściowych, wybranych zwierząt i ścieżek w ZOO oraz opisy ścieżek,
- oblicza, jaka jest minimalna liczba wybiegów, które trzeba odwiedzić wchodząc do ZOO dowolną bramą, następnie odwiedzając wybiegi zwierząt zgodnie z kolejnością, w jakiej te zwierzęta występują w opowieści (i nie odwiedzając żadnego zwierzęcia, przed zwierzętami, które występują przed nim w opowieści), i na koniec wychodząc przez dowolną bramę wyjściową,
- wypisuje minimalną liczbę wybiegów, które trzeba odwiedzić po drodze (powtarzające się wybiegi należy liczyć wielokrotnie) lub liczbę , gdy znalezienie takiej trasy nie jest możliwe.
Wejście
W pierwszym wierszu podane są liczby naturalne
oddzielone spacjami
,
,
,
,
).
Liczby te oznaczają: - liczbę wejść do ZOO, - liczbę wyjść z ZOO, - liczbę wybranych zwierząt, - liczbę wybiegów w ZOO, - liczbę ścieżek w ZOO.
W kolejnych wierszach podane są numery wybiegów wybranych zwierząt - po jednej liczbie w wierszu i zgodnie z kolejnością, w jakiej zwierzęta występują w opowieści
(każde zwierzę w ZOO może w niej wystąpić najwyżej jeden raz).
W następnych wierszach podane są opisy ścieżek -
po jednym w wierszu.
Opis ścieżki składa się z dwóch różnych liczb całkowitych oddzielonych spacją -
są to numery bram lub wybiegów połączonych bezpośrednio ścieżką.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy napisać:
- liczbę -1, jeżeli wyznaczenie trasy zgodnie z powyższymi zasadami nie jest możliwe lub
- liczbę naturalną, która oznacza minimalną liczbę wybiegów
(łącznie z tymi "interesującymi"), przez które musi przebiegać trasa
wyznaczona zgodnie z podanymi wyżej zasadami.
Przykład
Dla danych wejściowych:
2 4 1 2 9
6
4
1 3
2 3
1 4
3 7
3 5
4 5
6 5
4 6
7 6
poprawną odpowiedzią jest:
5